//
// Created by ASUS on 2024/1/9.
//
#include <bits/stdc++.h>
using namespace std;

const int MX=5e4+5;

class Trie{
	int next[MX][26],cnt;
	bool exist[MX];  // 该结点结尾的字符串是否存在

	void insert(string s) {  // 插入字符串
		int p = 0;
		for (int i = 0; i < s.length(); i++) {
			int c = s[i] - 'a';
			if (!next[p][c]) next[p][c] = ++cnt;  // 如果没有，就添加结点
			p = next[p][c];
		}
		exist[p] = 1;
	}

	bool find(string s) {  // 查找字符串
		int p = 0;
		for (int i = 0; i < s.length(); i++) {
			int c = s[i] - 'a';
			if (!next[p][c]) return 0;
			p = next[p][c];
		}
		return exist[p];
	}
};
